package 春招算法加速;


import java.util.Stack;

public class 反转链表 {
    /*
    输入一个链表，反转链表后，输出新链表的表头。
     */
    public static ListNode ReverseList(ListNode head) {
        //有条输入用例是输入空数据
        if (head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        //全部入栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        //第一个节点  3>2>1
        ListNode first = stack.pop();
        //下一个节点
        ListNode next = first;
        //全部出栈
        while (!stack.isEmpty()) {
            //把下一节点连接到本节点中
            next.next = stack.pop();
            //本节点跳为下一节点
            next = next.next;
        }
        //此时next为最后节点，原来连接倒数第二节点，设为null
        next.next = null;
        return first;
    }

    /*
    测试
     */
    public static void main(String[] args) {
        //插入假数据
        ListNode list1 = new ListNode();
        list1.data = 1;
        ListNode list2 = new ListNode();
        list2.data = 2;
        ListNode list3 = new ListNode();
        list3.data = 3;
        list1.next = list2;
        list2.next = list3;
        //输出数据
        ListNode list = list1;
        System.out.println(list.data);
        while (list.next != null) {
            list = list.next;
            System.out.println(list.data);
        }
        //调用算法反转
        list = ReverseList(list1);
        //输出结果
        System.out.println(list.data);
        while (list.next != null) {
            list = list.next;
            System.out.println(list.data);
        }
    }

    /*
    链表类
     */
    public static class ListNode {
        public ListNode() {
        }

        public ListNode next;
        public int data;
    }
}
